/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 示例:
 * <p>
 * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出: 6
 */
class Solution {

    public static void main(String[] args) {
        //System.out.println(trap(new int[]{1, 0, 2, 0, 1}));
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }

    public static int trap(int[] height) {
        return trap(height, 0, height.length - 1, 0);
    }

    public static int trap(int[] height, int x, int y, int sum) {
        if (height.length == 0 || y - x <= 1) return 0;
        int max = 0;
        int pos = 0;
        int min = Math.min(height[x], height[y]);
        for (int i = x + 1; i < y; i++) {
            if (height[i] >= min) {
                // 如果大于这两个的最小值
                if (max == 0 || (max != 0 && height[i] > max)) {
                    pos = i;
                    max = height[i];
                }
            }
        }
        if (pos == 0) {
            // 如果x和y之间没有比他们两个小的了，就结算
            sum += min * (y - x - 1);
            for (int i = 1; i < y - x; i++) {
                sum -= height[x + i];
            }
        } else {
            // 否则找到其中最大的递归下去
            return trap(height, x, pos, sum) + trap(height, pos, y, sum);
        }
        return sum;
    }


}